package LinkList;

/*
奇偶链表
给定单链表的头节点head，将所有索引为奇数的节点和索引为偶数的节点分别组合在一起，然后返回重新排序的列表。
第一个节点的索引被认为是 奇数 ， 第二个节点的索引为偶数 ，以此类推。
请注意，偶数组和奇数组内部的相对顺序应该与输入时保持一致。
你必须在O(1)的额外空间复杂度和O(n)的时间复杂度下解决这个问题。
示例 1:
输入: head = [1,2,3,4,5]
输出:[1,3,5,2,4]
示例 2:
输入: head = [2,1,3,5,6,4,7]
输出: [2,3,6,7,1,5,4]
作者：LeetCode
链接：https://leetcode.cn/leetbook/read/linked-list/fe0kj/
 */

public class _33奇偶链表 {
    public static void main(String[] args) {

    }

    public class ListNode {
        int val;
        ListNode next;

        ListNode() {
        }

        ListNode(int val) {
            this.val = val;
        }

        ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }
    }

    //双指针 + 长度判断 + dummy
    //有点像快慢双指针
    //时间复杂度 O(n)
    public ListNode oddEvenList(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode dummy = new ListNode(-1,head);
        ListNode pre = dummy;
        ListNode cur = head;
        ListNode evenhead = dummy.next.next;
        int count = 1;
        while (cur != null && cur.next != null) {
            ListNode next = cur.next;
            cur.next = cur.next.next;
            pre = cur;
            cur = next;
            count++;
        }
        if (count % 2 == 1) {
            cur.next = evenhead;
        }else {
            pre.next = evenhead;
        }

        return dummy.next;

    }

    //官解：分离节点后合并
    //正经双指针，每个指针代表一个链表  +  双dummy(？)
    //O(n)
    //优雅永不过时
//        public ListNode oddEvenList(ListNode head) {
//            if (head == null) {
//                return head;
//            }
//            ListNode evenHead = head.next;
//            ListNode odd = head, even = evenHead;
//            while (even != null && even.next != null) {
//                odd.next = even.next;
//                odd = odd.next;
//                even.next = odd.next;
//                even = even.next;
//            }
//            odd.next = evenHead;
//            return head;
//        }

}
